package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-29 10:06
 */
public class BF2024考试的最大困扰度 {

    public static void main(String[] args) {

        String answerKey = "FTFFTFTFTTFTTFTTFFTTFFTTTTTFTTTFTFFTTFFFFFTTTTFTTTTTTTTTFTTFFTTFTFFTTTFFFFFTTTFFTTTTFTFTFFTTFTTTTTTF";
        int k = 32;
        System.out.println(maxConsecutiveAnswers(answerKey, k));
    }


    /**
     * 5 3 4 6 7 1
     * k的值 可以将相邻的数值连接 最后数值中的最大值
     * 补全中间的值 可以将相邻的三个值合并  想要最大化肯定是只改一种奇数位或者偶数位时才能最大化
     * 所以分两种情况求分别求最大值 进行比较获取最大值即可
     * 怎么获取填补后的最大值呢？
     * 每经过一个坑时都有填和不填两种选择 将所有情况全部遍历一遍 获取最大值?回溯~~~~~
     * 终点是：
     * k小于坑值 或者n到终点
     *
     * 回溯层数多时 耗时很大 考虑用其他的方法代替
     * 滑动窗口:
     * 维护两个指针 left  right
     * 保证left right中间的坑数小于等于k 遍历每个右节点 最终获得最大值
     *
     *
     * @param answerKey
     * @param k
     * @return
     */
    public static int maxConsecutiveAnswers(String answerKey, int k) {
        if (answerKey.length() == 1
                || k > answerKey.length()) {
            return answerKey.length();
        }
        //1.将answerkey转换为数组
        int[] answerArray = new int[answerKey.length()];

        char flag = answerKey.charAt(0);
        int total = 1;
        int index = 0;
        for (int i = 1; i < answerKey.length(); i++) {
            if (flag == answerKey.charAt(i)) {
                total++;
            } else {
                answerArray[index] = total;
                index++;
                total = 1;
                flag = answerKey.charAt(i);
            }

            if (i == answerKey.length() - 1) {
                answerArray[index] = total;
            }
        }
        //接下来分两种情况进行处理 是同化奇数位还是偶数位
        int[] max = new int[1];
        odd(answerArray, index, 0, new ArrayList<>(), k, max);
        even(answerArray, index, 1, new ArrayList<>(), k, max);
        return max[0] < answerKey.length() ? max[0] : answerKey.length();
    }

    /**
     * 奇数位处理
     *
     * @return
     */
    private static void odd(int[] answerArray, int index, int start, List<Integer> list, int source, int[] max) {
        if (start > index || source <= 0) {
            //如果遍历完成 或者资源用完 则计算整个数组中的最大值
            int count = count(answerArray, index, list, false) + source;
            if (max[0] < count) {
                max[0] = count;
            }
            return;
        }
        if (source < answerArray[start]) {
            //说明资源已经不够用 可以跳过去
            odd(answerArray, index, start + 2, list, source, max);
            return;
        }
        list.add(start);
        odd(answerArray, index, start + 2, list, source - answerArray[start], max);
        list.remove(list.size() - 1);
        odd(answerArray, index, start + 2, list, source, max);
    }

    private static int count(int[] answerArray, int index, List<Integer> list, Boolean flag) {
        int max = 0;
        int total = 0;
        for (int i = 0; i <= index; i++) {
            //从第一位开始加 如果遇到中断则不再累加 重新计数
            if (!flag) {
                if (i % 2 != 0) {
                    total += answerArray[i];
                    if (i != index) {
                        continue;
                    }
                }
                if (list.contains(i)) {
                    total += answerArray[i];
                } else {
                    //第一个值不能丢掉
                    if (i == 0) {
                        total = answerArray[0];
                    }
                    if (max < total) {
                        max = total;
                        total = 0;
                    }
                }
                if (i == index) {
                    if (max < total) {
                        max = total;
                    }
                }
            } else {
                if (i % 2 == 0) {
                    total += answerArray[i];
                    continue;
                }
                if (list.contains(i)) {
                    total += answerArray[i];
                } else {
                    if (max < total) {
                        max = total;
                        total = 0;
                    }
                }
                if (i == index) {
                    if (max < total) {
                        max = total;
                    }
                }
            }
        }
        return max;
    }

    /**
     * 偶数位处理
     *
     * @return
     */
    private static void even(int[] answerArray, int index, int start, List<Integer> list, int source, int[] max) {
        if (start > index || source <= 0) {
            //如果遍历完成 或者资源用完 则计算整个数组中的最大值
            int count = count(answerArray, index, list, true) + source;
            //如果source还有剩余 则在任意位置计算出的最大值都可以加上剩余值(包含不合法的场景 但是那种场景肯定不会是最大值)
            if (max[0] < count) {
                max[0] = count;
            }
            return;
        }
        if (source < answerArray[start]) {
            //说明资源已经不够用 可以跳过去
            even(answerArray, index, start + 2, list, source, max);
            return;
        }
        list.add(start);
        even(answerArray, index, start + 2, list, source - answerArray[start], max);
        list.remove(list.size() - 1);
        even(answerArray, index, start + 2, list, source, max);
    }
}
